package middle;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import middle.Solution_71.CharacterType;

public class Solution_211 {

    public static void main(String[] args) {
        WordDictionary model = new Solution_211().new WordDictionary();
        model.addWord("at");
        model.addWord("and");
        model.addWord("an");
        model.addWord("add");
        System.out.println(model.search("a"));
        System.out.println(model.search(".at"));
        model.addWord("bat");
        System.out.println(model.search(".at"));
        System.out.println(model.search("an."));
        System.out.println(model.search("a.d."));
        System.out.println(model.search("b."));
        System.out.println(model.search("a.d"));
        System.out.println(model.search("."));
//        model.addWord("bad");
//        model.addWord("dad");
//        model.addWord("mad");
//        System.out.println(model.search("pad"));
//        System.out.println(model.search("bad"));
//        System.out.println(model.search(".ad"));
//        System.out.println(model.search("b.."));
    }

    class WordDictionary {
        private Node empty;

        public WordDictionary() {
            empty = new Node(' ');
        }

        public void addWord(String word) {
            Node node = empty;
            for (int i = 0; i < word.length(); i++) {
                if (node.map == null) {
                    node.map = new Node[26];
                }
                char c = word.charAt(i);
                Node child = node.map[c-'a'];
                if (child == null) {
                    child = new Node(c);
                    node.map[c-'a'] = child;
                }
                node = child;
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            return find(word.toCharArray(), 0, empty);
        }

        private boolean find(char[] chars, int index, Node node) {
            if (chars.length == index) {
                return node.isEnd;
            } else if (node.map == null) {
                return false;
            }
            char c = chars[index];
            if (c == '.') {
                for (Node child : node.map) {
                    if (child != null) {
                        boolean flag = find(chars, index + 1, child);
                        if (flag) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                Node child = node.map[c - 'a'];
                if (child == null) {
                    return false;
                }
                return find(chars, index + 1, child);
            }
        }

        class Node {
            public char c;
            public Node[] map;
            public boolean isEnd;

            public Node(char c) {
                this.c = c;
            }
        }
    }
}
